The present invention relates to the computation of branch metrics in Trellis Coded Modulation (“TCM”) communication systems. More specifically, the present invention relates to a computationally efficient, fast, and accurate way to calculate the branch metrics in a Viterbi decoder. The signal to be decoded can be any type of signal known in the art that uses TCM and/or Viterbi decoding. The present invention is ideally suited for satellite communication channels, for example channels employing MIL-STD-188-181b.
TCM and Viterbi decoders are well known in the art and have been described in detail in any number of books, papers, and articles, such as: Viterbi, A., “Convolutional Codes and Their Performance in Communication Systems,: IEEE Trans. Commun. Technol., vol. COM19, no. 5, October 1971, pp. 751–772; Heller, J. A., and Jacobs, I. W., “Viterbi Decoding for Satellite and Space Communication,” IEEE Trans. Commun. Technol., vol. COM19, no. 5. October 1971, pp. 835–848; Viterbi, A. J., and Omura, J. K., Principles of Digital Communication and Coding, McGraw-Hill Book Company, New York, 1979; all of which are hereby incorporated herein by reference.
Generally, TCM combines coding and modulation together at the transmitter where the coding scheme used is typically a convolutional code. At the receiver, the decoding and demodulation are typically performed in a single step with the receiver having a priori knowledge of the encoder's structure. In a TCM system where each symbol is to transmit k bits, some number m of the least significant bits are sent to an encoder which outputs m+p bits to map into the waveform which has p possible symbols, where p=2(k+p). The m−k bits are not encoded. The number of possible states that the encoder may have is dependent on the constraint length of the code. In a trellis representation of the waveform, the uncoded bits are represented as parallel paths in the transitions between trellis states. For optimum demodulation of the TCM, the parallel paths are followed through the trellis. This dramatically complicates the decoding of the Trellis Codes compared to normal convolutional codes because branch metrics have to be computed for all the parallel paths, and the best parallel path needs to be stored for all surviving paths.
Generally, a Viterbi decoder performs maximum likelihood decoding but reduces the computational burden by taking advantage of the structure of the trellis. The decoder calculates the “distance”, or branch metric, between the received signal at time ti and all the trellis paths entering each state at time ti. The decoder eliminates those trellis paths that are not candidates for the maximum likelihood choice. When two paths enter the same state, the path with the best metric is chosen and the other path is discarded. Maximum likelihood decoding can equivalently be expressed as minimum distance decoding.
For trellis codes, the number of branch metrics that need to be calculated is a function of the complexity of the code. The more complex the code, the larger and more complicated the trellis, the more branch metrics need to be computed for any given state transition, and the higher the burden on the processor at the receiver. Additionally, the receiver processor may additionally be tasked with computations related to other functions, such as tracking algorithms.
Typical prior art solutions to the problem of processor burden include increasing the size and/or computational capacity and/or speed of the processor. However, these solutions have the disadvantage of requiring more power to drive the processor and therefore are not practical for power-limited devices, such as hand-held receivers or other devices that operate from battery power.
For example, the computation of branch metrics for a MIL-STD-188-181b signal requires 64 distance calculations on complex numbers at rates of up to 32 KHz per set. With the time and frequency tracking algorithms also running and the computations being handled by the same processor, the processor is likely to be strained and perhaps extended beyond its capacity to function in a timely manner.
One possibility for reducing the burden on the processor is to remove the branch metric calculations from the list of computations to be performed by the processor. The invention described herein reduces the processor burden by use of a look-up table for extracting the branch metric values. Specifically, the present inventive system and method uses a look-up table that is indexed with polar coordinates. In one embodiment, the polar coordinates for accessing the branch metric values in the look-up table may be obtained from an intermediate frequency application specific integrated circuit (“ASIC”). The ASIC may produce polar coordinates from the Cartesian coordinates of a symbol in the intermediate frequency signal. It is to be understood that the use of an ASIC to obtain the polar coordinates is just one exemplary method of producing the polar coordinates and that any method of producing polar coordinates of a received symbol, from an intermediate frequency or elsewhere, for use in accessing the branch metric values in the look-up table is contemplated by the present inventive system and method. The decoding algorithm itself can perform the access of the table on the fly, which significantly reduces the software complexity and further relieves the processor computational burden.
In one embodiment using a Minimum Distance Decoder, the look-up table contains all the possible distances for any received waveform relative to a reference waveform. When a symbol is received, that symbol is used to offset the index of the symbol represented by the state of the decoder. When the signal is close to the symbol corresponding to the decoder state, the offset index references distances of symbols that are close to the reference. These distances are typically small. Similarly, when the received signal is different from the state of the decoder, the index will reference large distances. In another embodiment using a Maximum Correlation Decoder, the same technique may be used by simply changing the generation of the look-up table, e.g., multiplying the Cartesian coordinates of the received symbol by the complex conjugate of the Cartesian coordinates of a reference point and extracting the real portion of the product. This technique will be discussed in more detail below.
Thus there is a need for determining branch metric values which can avoid the requirement of increasing the computational capacity and therefore the power consumption of the receiver processor.
Accordingly, it is an object of the present invention to obviate many of the above problems in the prior art and to provide a novel system and method for determining branch metric values without increasing the computational capacity and/or power consumption of the receiver processor.
It is another object of the present invention to provide a novel system and method for generating a branch metric look-up table indexed by polar coordinates.
It is yet another object of the present invention to provide a novel system and method for determining branch metric values for a phase shift keyed waveform.
It is still another object of the present invention to provide a novel system and method for determining branch metric values for a continuous phase modulated waveform.
It is a further object of the present invention to provide a novel system and method for determining branch metric values for a quadrature amplitude modulated waveform.
It is still a further object of the present invention to provide a novel system and method for determining branch metric values by defining a first locus of points as known candidate symbols and a second locus of points as potential received symbols and assigning a received symbol to the nearest potential received symbol point.
It is yet a further object of the present invention to provide a novel system and method for determining branch metric values for a Viterbi decoder by accessing a look-up table containing branch metric values for known candidate symbols and potential received symbols where the look-up table is indexed by a polar coordinate of the received symbol.
These and many other objects and advantages of the present invention will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims, the appended drawings, and the following detailed description of the preferred embodiments.